#include "AC.h"

bool visitada(int ciudad, vector<int> visitadas) {

	for (int i = 0; i < visitadas.size(); i++) {
		if (ciudad == visitadas[i])
			return true;
	}

	return false;
}

double updateSumatoria(Solution *s, int i, vector<int> visitadas, double** t,
		double alpha, double betha) {
	double sumatoria = 0.0;

	for (int z = 1; z <= s->cityNumber; z++) {
		if (!visitada(z, visitadas)) {
			int mini = min(i - 1, z - 1);
			int maxi = max(i - 1, z - 1);
			sumatoria += pow(t[mini][maxi], alpha) * pow((10.0
					/ s->C[mini][maxi]), betha);
		}
	}
	return sumatoria;
}

double** newMD(int size) {

	double** LT;
	LT = new double*[size];

	for (int i = 0; i < size; i++)
		LT[i] = new double[size];

	for (int i = 0; i < size; i++)
		for (int j = 0; j < size; j++)
			LT[i][j] = 0;

	return LT;
}

double** newT(int size, Solution* s, double tmax) {

	double** LT;
	LT = new double*[size];

	for (int i = 0; i < size; i++)
		LT[i] = new double[size];

	for (int i = 0; i < size; i++)
		for (int j = i+1; j < size; j++) {
			//if (i < j)
				LT[i][j] = tmax;
			//else
				//LT[i][j] = 0;
		}
	return LT;
}

double** updateFeromona2(Solution *sMejor, Solution *sHormiga, double **t,
		double prob, double tmax, double tmin) {

	double dM = 1.0 / sMejor->cost;
	double d = 1.0 / sHormiga->cost;

	int ini;
	int fin = ini = 0;

	for (int q = 0; q < sMejor->cityNumber - 1; q++) {
		ini = min(sHormiga->tour[q], sHormiga->tour[q + 1]) - 1;
		fin = max(sHormiga->tour[q], sHormiga->tour[q + 1]) - 1;

		if (t[ini][fin] > tmax)
			t[ini][fin] = tmax;
		else if (t[ini][fin] < tmin)
			t[ini][fin] = tmin;
		else
			t[ini][fin] = prob * t[ini][fin] + d;

		ini = min(sMejor->tour[q], sMejor->tour[q + 1]) - 1;
		fin = max(sMejor->tour[q], sMejor->tour[q + 1]) - 1;

		if (t[ini][fin] > tmax)
			t[ini][fin] = tmax;
		else if (t[ini][fin] < tmin)
			t[ini][fin] = tmin;
		else
			t[ini][fin] = prob * t[ini][fin] + dM;
	}

	ini = min(sHormiga->tour[0], sHormiga->tour[sMejor->cityNumber - 1]) - 1;
	fin = max(sHormiga->tour[0], sHormiga->tour[sMejor->cityNumber - 1]) - 1;

	if (t[ini][fin] > tmax)
		t[ini][fin] = tmax;
	else if (t[ini][fin] < tmin)
		t[ini][fin] = tmin;
	else
		t[ini][fin] = prob * t[ini][fin] + d;

	ini = min(sMejor->tour[0], sMejor->tour[sMejor->cityNumber - 1]) - 1;
	fin = max(sMejor->tour[0], sMejor->tour[sMejor->cityNumber - 1]) - 1;

	if (t[ini][fin] > tmax)
		t[ini][fin] = tmax;
	else if (t[ini][fin] < tmin)
		t[ini][fin] = tmin;
	else
		t[ini][fin] = prob * t[ini][fin] + dM;

	return t;

}
double** updateFeromona(Solution *sMejor, double **t, double tmax, double tmin,
		double prob) {

	double deltha = 100.0 / sMejor->cost;

	for (int q = 0; q < sMejor->cityNumber; q++) {
		int ini;
		int fin;

		if (q == sMejor->cityNumber - 1) {
			ini = min(sMejor->tour[0], sMejor->tour[q - 1]) - 1;
			fin = max(sMejor->tour[0], sMejor->tour[q - 1]) - 1;
		} else {
			ini = min(sMejor->tour[q], sMejor->tour[q + 1]) - 1;
			fin = max(sMejor->tour[q], sMejor->tour[q + 1]) - 1;
		}

		if (t[ini][fin] > tmax)
			t[ini][fin] = tmax;
		else if (t[ini][fin] < tmin)
			t[ini][fin] = tmin;
		else
			t[ini][fin] = t[ini][fin] * prob + deltha;
	}

	return t;
}

double calcularCosto(Solution *s) {

	for (int x = 0; x <= s->cityNumber - 1; x++) {
		if (x == s->cityNumber - 1)
			s->cost += s->getCost(0, x);
		else
			s->cost += s->getCost(x, x + 1);
	}

	return s->cost;
}

double cityNext(Solution* s, int i, double** p) {

	double elegido = ((double) rand() / (RAND_MAX));
	double acumulado = 0.0;

	//Se toma el sucesor aleatorio
	for (int z = 1; z <= s->cityNumber; z++) {
		int mini = min(i, z) - 1;
		int maxi = max(i, z) - 1;

		if (elegido <= p[mini][maxi] + acumulado)
			return z;
		else
			acumulado += p[mini][maxi];
	}

}

Solution* AC::AntColony(Solution* is, int maxIter, int numAnt, double t0,
		double alpha, double betha) {

	Solution *sMejor = is->clone();
	Solution *sHormiga = is->clone();
	Solution *s = is;

	srand((unsigned) time(NULL));

	double** p = newMD(is->cityNumber);
	double** t = newT(is->cityNumber,is,t0);

	double prob = 0.4; //Probabilidad
	//double pF = 1.0; //Porcentaje de evaporacion

	for (int numIter = 0; numIter <= maxIter; numIter++) {
		vector<int> visitadas;

		for (int k = 0; k <= numAnt; k++) {
			visitadas.clear();

			//Ciudad inicial
			int inicial = rand() % (is->cityNumber);
			int i = inicial += 1;

			s->tour[0] = inicial;


			//Colocamos la ciudad inicial como visitada
			visitadas.push_back(inicial);

			int j;
			int actual = 1;
			double mejor = 0.0;

			/*Se arma el camino creo que para cada j no visitada calculo los gastos y veo
			 * cual es la mas barata entonces esa sera la sucesora de i*/

			while (visitadas.size() < s->cityNumber) {
				double sumatoria = updateSumatoria(s, i, visitadas, t, alpha,
						betha);

				for (j = 1; j <= s->cityNumber; j++) {
					int mini = min(i - 1, j - 1);
					int maxi = max(i - 1, j - 1);

					if (!visitada(j, visitadas)) {
						p[mini][maxi] = (pow(t[mini][maxi], alpha) * pow((10.0
								/ s->C[mini][maxi]), betha)) / sumatoria;
					} else {
						p[mini][maxi] = 0;
					}
				}

				j = cityNext(s, i, p);
				visitadas.push_back(j); //La marco como visitada
				i = j; //La coloco como nueva ciudad actual

				s->tour[actual] = j;


				actual++;
			}

			s->cost = 0.0;
			s->cost = calcularCosto(s);

			if (s->cost < sMejor->cost)
				sMejor = s->clone();

			if (k == 0)
				sHormiga = s->clone();
			else if (s->cost < sHormiga->cost)
				sHormiga = s->clone();

			//Evaporacion de Feromona
			for (int q = 0; q < s->cityNumber; q++) {
				for (int l = q + 1; l < s->cityNumber; l++) {
					t[q][l] = (1 - prob) * t[q][l];
				}
			}//Fin Evaporacion

			//Actualizo Feromona
			t = updateFeromona(s, t, 1000, 0, prob);

		}//Fin Hormigas

		//Actualizo Feromona de la mejor hormiga
		t = updateFeromona2(sMejor, sHormiga, t, prob, 1000, 0);

	}

	for (int i = 0; i < is->cityNumber; i++) {
		delete[] t[i];
		delete[] p[i];
	}
	delete[] t;
	delete[] p;

	delete sHormiga;
	delete s;

	return sMejor;
}

Solution* AC::AntColonyMinMax(vector<Node> nodelist, int maxIter, int numAnt,
		double tmax, double tmin, double alpha, double betha) {

	Solution *s = new Solution(nodelist.size(), nodelist);
	Solution *sMejor = s->clone();
	Solution *sHormiga = new Solution(s->cityNumber);

	srand((unsigned) time(NULL));

	double** p = newMD(s->cityNumber);
	double** t = newT(s->cityNumber, s, tmax);

	double prob = 0.3; //Probabilidad
	//double pF = 1.0; //Porcentaje de evaporacion

	cout << s->cost << endl;

	vector<int> visitadas;

	for (int numIter = 0; numIter < maxIter; numIter++) {

		for (int k = 0; k < numAnt; k++) {
			//visitadas.clear();

			//Ciudad inicial
			int inicial = rand() % (s->cityNumber);
			int i = inicial += 1;

			s->tour[0] = inicial;

			//Colocamos la ciudad inicial como visitada
			visitadas.push_back(inicial);

			int j;
			int actual = 1;
			double mejor = 0.0;

			/*Se arma el camino creo que para cada j no visitada calculo los gastos y veo
			 * cual es la mas barata entonces esa sera la sucesora de i*/

			while (visitadas.size() < s->cityNumber) {

				double sumatoria = updateSumatoria(s, i, visitadas, t, alpha,
						betha);

				for (j = 1; j <= s->cityNumber; j++) {
					int mini = min(i, j) - 1;
					int maxi = max(i, j) - 1;

					if (!visitada(j, visitadas)) {
						p[mini][maxi] = (pow(t[mini][maxi], alpha) * pow((10.0
								/ s->C[mini][maxi]), betha)) / sumatoria;
					} else {
						p[mini][maxi] = 0.0;
					}

					t[mini][maxi] = (1 - prob) * t[mini][maxi];
				}

				j = cityNext(s, i, p);

				visitadas.push_back(j); //La marco como visitada

				i = j; //La coloco como nueva ciudad actual

				s->tour[actual] = j;

				actual++;
			}

			s->cost = 0.0;
			s->cost = calcularCosto(s);
			if (s->cost < sMejor->cost) {
				for (int q = 0; q < s->cityNumber; q++) {
					sMejor->tour[q] = s->tour[q];
				}
				sMejor->cost = s->cost;
			}

			if (k == 0) {
				for (int q = 0; q < s->cityNumber; q++) {
					sHormiga->tour[q] = s->tour[q];
				}
				sHormiga->cost = s->cost;
			} else if (s->cost < sHormiga->cost) {
				for (int q = 0; q < s->cityNumber; q++) {
					sHormiga->tour[q] = s->tour[q];
				}
				sHormiga->cost = s->cost;
			}

			visitadas.clear();

			//Evaporacion de Feromona
			/*for (int q = 0; q < s->cityNumber; q++) {
				for (int l = q + 1; l < s->cityNumber; l++) {
					t[q][l] = (1 - prob) * t[q][l];
				}
			}*///Fin Evaporacion

		}//Fin Hormigas

		//Actualizo Feromona de la mejor hormiga
		t = updateFeromona(sHormiga, t, tmax, tmin, prob);

	}

	for (int i = 0; i < s->cityNumber; i++) {
		delete[] t[i];

		delete[] p[i];
	}
	delete[] t;
	delete[] p;

	delete sHormiga;
	delete s;

	for (int q = 0; q < s->cityNumber; q++) {
		cout << sMejor->tour[q] << "-";
	}
	cout << endl;
	return sMejor;
}

